// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-03-02 21:33
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class ReconstructQueue {
    //    public int[][] reconstructQueue(int[][] people) {
//        // 从低到高进行考虑
//        int n = people.length;
//        int[][] ans = new int[n][]; // 可变长二维数组
//        Arrays.sort(people, new Comparator<int[]>() {
//            @Override
//            public int compare(int[] x, int[] y) {
//                if (x[0] != y[0]) { // 两个人的身高不一样
//                    return x[0] - y[0]; // 按照身高进行降序排序
//                } else {
//                    return y[1] - x[1]; // 按照ki进行升序排序
//                }
//            }
//        });
//        for (int[] person : people) {
//            int space = person[1] + 1;
//            for (int i = 0; i < n; i++) {
//                if (ans[i] == null) {
//                    --space;
//                }
//                if (space == 0) {
//                    ans[i] = person;
//                    break;
//                }
//            }
//        }
//        return ans;
//
//    }
    public int[][] reconstructQueue(int[][] people) {
        // 从高到低进行考虑,从前到后
        int n = people.length;
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] x, int[] y) {
                if (x[0] != y[0]) {
                    return y[0] - x[0];
                } else {
                    return x[1] - y[1];
                }
            }
        });
        ArrayList<int[]> ans = new ArrayList<>();
        for (int[] person : people) {
            ans.add(person[1], person);  // 因为数组元素是按照身高从高往低排列，所以数组后面的元素并不会影响到数组前面的k值
            // 而且根据List列表中插入的自动对序号的变化的特性，使得数据的插入在对k值没有影响的情况下实现了index的变化
        }
        return ans.toArray(new int[ans.size()][]);

    }
}
